/**
 * 2
3.3 
栈
1. 用数组实现顺序栈，支持 push、pop、peek、isEmpty、isFull，处理栈空 / 满时的操作异常。
测试用例：push (1,2,3)→peek ()=3→pop ()=3→pop ()=2→栈内剩 [1]。
2. 用栈实现 "字符串反转"：输入 "hello"，输出 "olleh"；输入 "abcde"，输出 "edcba"。

 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>


//用数组实现顺序栈
typedef struct ArrayStack{
    int* data;
    int top;
    int capacity;
}ArrayStack;

// 初始化栈
ArrayStack* createStack(int capacity) {
    ArrayStack* stack = (ArrayStack*)malloc(sizeof(ArrayStack));
    if(stack==NULL)
    {
        printf("内存分配失败\n");
        exit(1);
    }
    stack->capacity = capacity;
    stack->top = -1;
    stack->data = (int*)malloc(capacity * sizeof(int));
    if(stack->data == NULL){
        printf("内存分配失败\n");
        free(stack);
        exit(1);
    }
    return stack;
}

// 检查栈是否为空
bool isEmpty(ArrayStack* stack) {
    return (stack->top == -1);
}

// 检查栈是否已满
bool isFull(ArrayStack* stack) {
    return (stack->top == stack->capacity-1);
}

// 入栈操作
void push(ArrayStack* stack, int value) {
    if(isFull(stack)){
        printf("错误：栈已满，无法入栈\n");
        return;
    }
    stack->data[++stack->top] = value;
}

// 出栈操作
int pop(ArrayStack* stack) {
    if(isEmpty(stack))
    {
        printf("错误：栈为空，无法出栈\n");
        exit(1);  // 实际应用中可返回特定值或使用错误码
    }

    return stack->data[stack->top--];
}

// 获取栈顶元素（不弹出）
int peek(ArrayStack* stack) {
    if(isEmpty(stack))
    {
        printf("错误：栈为空，无法peek\n");
        exit(1);  // 实际应用中可返回特定值或使用错误码
    }
    return stack->data[stack->top];
}

// 释放栈内存
void freeStack(ArrayStack* stack) {
    free(stack->data);
    free(stack);
}

// 测试顺序栈
void testStack() {
    /**
     * 1. 用数组实现顺序栈，支持 push、pop、peek、isEmpty、isFull，处理栈空 / 满时的操作异常。
测试用例：push (1,2,3)→peek ()=3→pop ()=3→pop ()=2→栈内剩 [1]。
     */
    ArrayStack* stack = createStack(3);
    push(stack,1);
    
    push(stack,2);
    push(stack,3);

    printf("[%d]\n",peek(stack));

    pop(stack);

    pop(stack);

    printf("[%d]\n",peek(stack));

}

/**
 * 2. 用栈实现 "字符串反转"：输入 "hello"，输出 "olleh"；输入 "abcde"，输出 "edcba"。
 */
// 字符串反转函数（基于栈实现）
char* reverseString(const char* str) {
    int len = strlen(str);//strlen不会计算\0
    ArrayStack* strStack = createStack(len);//!!!!!!free()
    for(int i=0;i<len;i++)
    {
        push(strStack,str[i]);
    }
    char* reverseString =(char*)malloc(len+1);
    for(int i=0;i<len;i++)
    {
        reverseString[i]= pop(strStack);
    }
    reverseString[len] = '\0';
    free(strStack);//!!!!!!!!!!!!!!
    return reverseString;
}
void myprint_str(char* str){
    int i=0;
    while(str[i]!='\0'){
        printf("%c",str[i++]);
    }
    printf("\n");
}
void test2(){
    const char str[]={"HELLO"}; 
    myprint_str(reverseString(str));
    const char str1[]={"abcde"}; 
    myprint_str(reverseString(str1));
}
int main(){
    testStack();
    test2();

}